#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "utils.h"

#define MAX 1048576
int Hex2Char(unsigned int fromi, unsigned char *toc)
{
	if (fromi >= 0 && fromi <= 9)
		*toc = fromi + '0';
	else if (fromi >= 10 && fromi <= 15)
		*toc = fromi - 10 + 'A';
	else
		printf("error!\n");
}

int Char2Hex(unsigned char fromc, unsigned int *toi)
{
	if (fromc >= '0' && fromc <= '9')
		*toi = fromc - '0';
	else if (fromc >= 'A' && fromc <= 'F')
		*toi = fromc - 'A' + 10;
	else
		printf("error");

	return 0;
}

int Bitstr2ByteArr(unsigned char *bs, unsigned char *ba, int *lba)
{
	//计算长度
	int i = 0; //原始长度
	for (; bs[i] != '\0'; i++)
		;
	int blen = (i + 7) / 8; // byte length
	*lba = blen;
	int clen = blen * 8; // fix bit length
	//填充并字符转数值
	char *temp = (char *)malloc(clen + 1);
	for (int j = 0; j < i; j++)
	{
		temp[clen - i + j] = bs[j] - '0';
	}
	for (int j = 0; j < clen - i; j++)
	{
		temp[j] = 0;
	}
	for (int j = 0; j < blen; j++)
	{
		for (int k = 0; k < 8; k++)
		{
			ba[j] = temp[8 * j + k] + (ba[j] << 1);
		}
	}
	return 0;
}

int ByteArr2Bitstr(unsigned char *ba, unsigned char *bs, int *lbs)
{
	int i = 0;
	for (; ba[i] != '\0'; i++)
		;
	*lbs = i;

	for (int j = 0; j < i; j++)
	{
		for (int k = 0; k < 8; k++)
		{
			bs[j * 8 + 7 - k] = (ba[j] & 1) + '0';
			ba[j] = ba[j] >> 1;
		}
	}
}

//整型转字节数组
int Int2ByteArr(unsigned int i, unsigned char *ba)
{
	for (int j = 0; i != 0; j++)
	{
		ba[3 - j] = i & 255;
		i = i >> 8;
	}
}

//字节数组转整型
int ByteArr2Int(unsigned char *ba, unsigned int *i)
{
	*i = (ba[0] << 24) + (ba[1] << 16) + (ba[2] << 8) + ba[3];
}

// Eratosthene小素数筛选法
int SmallPrimeList(int n, int *plist, int *len)
{
	assert(n >= 2 && n <= MAX);
	int b[n];

	for (int i = 0; i < n + 1; i++)
	{
		b[i] = 1;
	}

	for (int i = 2; i * i <= n; i++)
	{
		for (int k = 2; k <= n / i; k++)
		{
			int j = i * k;
			b[j] = 0;
		}
	}

	int nlen = 0;
	for (int i = 0; i <= n; i++)
	{
		nlen = nlen + b[i];
	}
	nlen = nlen - 2;
	*len = nlen;

	for (int i = 2, j = 0; i <= n; i++)
	{
		if (b[i] == 1)
			plist[j++] = i;
	}
}

//拓展的欧几里得算法
int ExtendedGCD(int a, int b, int *k, int *u, int *v)
{
	assert(a >= 0 && b >= 0);

	int a0, a1, b0, b1, c, d, q, r, t;
	a1 = b0 = 1;
	a0 = b1 = 0;
	c = a;
	d = b;

	q = c / d;
	r = c % d;
	while (r)
	{
		c = d;
		d = r;
		t = a1;
		a1 = a0;
		a0 = t - q * a0;
		t = b1;
		b1 = b0;
		b0 = t - q * b0;

		q = c / d;
		r = c % d;
	}
	*u = a0;
	*v = b0;
	*k = d;

	return 0;
}
